package warm100;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class decodeString_394 {
    public String decodeString(String s) {
        //并非一定是这种数字加中括号的格式 "3[a]2[bc]"
        // "3[a2[c]]"  abc3[cd]xyz
        //核心找数字和[]，压入数字，每遇到一个右括号弹出一个数字 进行对中间的字符串处理后再压进栈内
        int num = 0;
        Stack<StringBuilder> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c - '0' <= 9 && c - '0' >= 0) {  //遇到数字进行计算
                num = num * 10 + s.charAt(i) - '0';
            } else if (c == '[') {
                stack.push(new StringBuilder(String.valueOf(num)));  //压入数字
                num =  0 ;
            } else if (c == ']') {
                StringBuilder temp1 = stack.pop();
                StringBuilder temp2 = new StringBuilder();
                int k = Integer.parseInt(stack.pop().toString());  //数字
                while (k-- != 0)
                    temp2.append(temp1);      //得到处理完的字符串
                merge(stack, temp2);                 //压入栈内
            } else                               //遇到字符
                merge(stack, new StringBuilder(String.valueOf(s.charAt(i))));
        }
        return stack.pop().toString();
    }

    /**
     * 将字符串加入栈中，同时保证栈中没有连续独立的字符串
     */
    public void merge(Stack<StringBuilder> stack, StringBuilder sb) {
        StringBuilder temp = new StringBuilder();
        StringBuilder temp1 = new StringBuilder();
        temp.append(sb);
        //保证栈中每个 【  右边只有一个字符串
        if (!stack.isEmpty() && stack.peek().charAt(0) - '0' > 9) { //栈顶不为数字
            temp1 = stack.pop();
            temp = temp1.append(temp);
        }
        stack.push(temp);
    }

    /**
     * 简洁思路
     */
    public String decodeString2(String s) {
        Stack<Integer> stack_num = new Stack<>(); // 存储需要重复字符串的数字
        Stack<String> stack_res = new Stack<>();      // 存储待重复的字符串
        StringBuilder res = new StringBuilder();     //记录实时连续的字符串
        int num = 0;
        //"3[a2[c]]"
        for (Character x : s.toCharArray()) {
            if (x == '[') {
                stack_num.push(num); // 把  [  前的数字压栈
                stack_res.push(res.toString()); //把  [  前的字母——即会被重复的中间部分字符串压栈  如例子中的 a

                //需重复数字归零（注意！因为 num 可能会是n位数，为了方便后续统一x10处理，必须归零
                num = 0;
                res = new StringBuilder();       // res 也要重置

            } else if (x == ']') {

                int cur_num = stack_num.pop();      //此次要重复的次数数字
                String last_res = stack_res.pop();     //在  [  左边的还没执行重复的字符串

                StringBuilder tmp = new StringBuilder(); // 本次重复 cur_num 次的完整子串
                for (int i = 0; i < cur_num; i++)
                    tmp.append(res);

                res = new StringBuilder(last_res + tmp); //  [  左右两部分字符串连接

            } else if (x >= '0' && x <= '9')
                num = num * 10 + (x - '0'); // 把字符数字转换为数字

            else     //连续的字母
                res.append(x);
        }

        return res.toString();
    }
}
